package com.cyx;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

/**
 * @author 陈裕星
 * @version 1.0
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 */
public class 电话号码的字母组合 {
    static HashMap<Character, String> map;
    static List<Character> list = new ArrayList<>();
    static List<String> res = new ArrayList<>();
    public static void main(String[] args) {
        //先构建一个字母与数字映射的集合
        map = new HashMap<>();

        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");

        Scanner sc = new Scanner(System.in);
//        String digits = sc.next();
        //采用递归回溯法
        String digits = "";
        helper(digits,0);

        System.out.println(res.toString());
        System.out.println(res.size());
    }
    static void helper(String digits,int start){
        if(list.size() == digits.length()){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < list.size(); i++){
                sb.append(list.get(i));
            }
            res.add(sb.toString());
            return;
        }
        String s = map.get(digits.charAt(start));
        for (int j = 0; j < s.length(); j++){
            list.add(s.charAt(j));
            //递归
            helper(digits,start+1);
            //回溯
            list.remove(list.size()-1);
        }
    }
}
